class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size(), left1 = 0, left2 = 0, right = 0, sum1 = 0,
            sum2 = 0, ans = 0;
        for (; right < n; right++) {
            sum1 += nums[right];
            while (left1 <= right && sum1 > goal) {
                sum1 -= nums[left1++];
            }
            sum2 += nums[right];
            while (left2 <= right && sum2 >= goal) {
                sum2 -= nums[left2++];
            }
            ans += (left2 - left1);
        }
        return ans;
    }
};
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size(), left1 = 0, left2 = 0, right = 0, sum1 = 0,
            sum2 = 0, ans = 0;
        for (; right < n; right++) {
            if(nums[right]%2) sum1++,sum2++;
            while (left1 <= right && sum1 > k) {
                if(nums[left1++]%2) sum1--;
            }
            while (left2 <= right && sum2 >= k) {
                if(nums[left2++]%2) sum2--;
                
            }
            ans += (left2 - left1);
        }
        return ans;
    }
};
int fun(vector<int>& window) {
    bool a =
        window['a'] && window['e'] && window['i'] && window['o'] && window['u'];
    if (a == false)
        return 100000;
    return window['a'] + window['e'] + window['i'] + window['o'] + window['u'];
}
class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        int n = word.size();
        vector<int> window1(256);
        vector<int> window2(256);
        int left1 = 0, left2 = 0;
        long long ans = 0;
        for (int right = 0; right < n; right++) {
            window1[word[right]]++;
            window2[word[right]]++;
            while (fun(window1) + k < right - left1 + 1) {
                window1[word[left1++]]--;
            }
            while (fun(window2) + k <= right - left2 + 1) {
                window2[word[left2++]]--;
            }
            // cout << fun(window2) << ' ';
            ans += left2 - left1;
        }
        return ans;
    }
};
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int left1 = 0, left2 = 0, n = nums.size(), ans = 0;
        unordered_map<int, int> mm1, mm2;
        for (int right = 0; right < n; right++) {
            mm1[nums[right]]++, mm2[nums[right]]++;
            while (mm1.size() > k) {
                int tmp = nums[left1++];
                if (--mm1[tmp] == 0)
                    mm1.erase(tmp);
            }
            while (mm2.size() >= k) {
                int tmp = nums[left2++];
                if (--mm2[tmp] == 0)
                    mm2.erase(tmp);
            }
            // cout << left1 <<' ' << left2 <<' ' << right << endl;
            ans += left2 - left1;
        }
        return ans;
    }
};